package _0572_Subtree_of_Another_Tree;

/**
 * Date: 2021/9/25 14:05
 * Content:
 * 执行用时：3 ms, 在所有 Java 提交中击败了86.49%的用户
 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了20.91%的用户
 */
public class Solution {

    public boolean isSubtree(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        if (isPart(A, B)) return true;
        return isSubtree(A.left, B) || isSubtree(A.right, B);
    }

    private boolean isPart(TreeNode A, TreeNode B) {
        if (A == null && B == null) return true;
        if (A == null || B == null) return false;
        if (A.val != B.val) return false;
        return isPart(A.left, B.left) && isPart(A.right, B.right);
    }

    public static void main(String[] args) {

        int nu = Integer.MIN_VALUE;  // 用Integer.MIN_VALUE表示二叉树 null
        int[] nums1 = {
                3,
                4, 5,
                1, 2, nu, nu,
                nu, nu, 0
        };
        int[] nums2 = {
                4,
                1, 2
        };
        TreeNode A = (new MyTree(nums1)).getRoot();
        TreeNode B = (new MyTree(nums2)).getRoot();
        System.out.println((new Solution()).isSubtree(A, B));  // false
    }
}
